#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2017 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""
    李白喝酒的问题: 递归求解
    李白街上走, 提壶去买酒, 遇店加一倍,见花喝一斗”，
    途中，遇见5次店，见了10此花，壶中原有2斗酒，最后刚好喝完酒.
    要求最后遇见的是花.

    https://blog.csdn.net/m0_38033475/article/details/79247029
"""

wineInit   = 2       # 2斗酒
shopInit   = 5       # 遇店加一倍:　遇到5次
flowerInit = 10      # 遇花喝1斗:   遇到10次花

kSolution = 1       # 遇到解
kInValid  = 2       # 当前非解: 并且继续也不可能遇到解(趁早剪枝)
kGo       = 3       # 当前非解: 继续走, 可能遇到解


def check(wineCnt, shopCnt, flowerCnt):

    if( wineCnt == 0 and shopCnt == 0 and flowerCnt == 0 ):
        return kSolution

    elif ( wineCnt < 0 or shopCnt < 0 or flowerCnt < 0 ):
        return kInValid

    elif ( wineCnt <= 0 and flowerCnt > 0 ):
        return kInValid

    elif (wineCnt <= 0 and shopCnt > 0):        # 要求最后遇见的是花
        return kInValid

    else:
        return kGo;


solutionCnt = 0     #　解计数
def PrintSolution(solutionPath):
    global solutionCnt
    solutionCnt += 1
    print solutionCnt, solutionPath


def  drinkWine(wineCnt, shopCnt, flowerCnt, partPath):
    valid = check(wineCnt, shopCnt, flowerCnt)

    if (valid == kSolution):
        PrintSolution(partPath)
        return

    elif (valid == kInValid):
        return

    # valid == kGo
    drinkWine(wineCnt * 2, shopCnt - 1, flowerCnt, partPath + "s")   # "s" : shop
    drinkWine(wineCnt - 1, shopCnt , flowerCnt - 1, partPath + "f")  # "f" : flower


drinkWine(wineInit, shopInit, flowerInit, "")
